package com.mengfou.sortextends;

/**
 * 快排的三个版本
 *
 * @author mengfou
 */
public class QuickSortVersions {

    public static void main(String[] args) {
        int[] arr2 = new int[]{1, 4, 4, 4, 1, 0, 4, 6, 3, 4, 7, 4, 8, 0, 1, 4};
        long curTime = System.currentTimeMillis();
        new QuickSortVersions().quickSortVersion_3(arr2);
        System.out.println("Version_2 耗时：" + (System.currentTimeMillis() - curTime));
        printArray(arr2);
    }

    private static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }

    /**
     * 快排版本1，即选择左边或者右边的端点值来作为轴值，然后进行改数的最终位置的放置，并将数据划分为两个部分
     *
     * @param arr 待排序数组
     */
    public void quickSortVersion_1(int[] arr) {
        if (arr == null || arr.length == 0) return;
        quickSortV_1(arr, 0, arr.length - 1);
    }

    private void quickSortV_1(int[] arr, int left, int right) {
        if (left < right) {
            int mid = partitionV_1(arr, left, right);
            quickSortV_1(arr, left, mid - 1);
            quickSortV_1(arr, mid + 1, right);
        }
    }

    private int partitionV_1(int[] arr, int left, int right) {
        int value = arr[left];
        while (left < right) {
            while (left < right && arr[right] > value) right--;
            swap(arr, left, right);
            while (left < right && arr[left] <= value) left++;
            swap(arr, left, right);
        }
        return left;
    }


    /**
     * 快排第二个版本，改动部分为partition，也就是将数据划分为了三个部分，小于轴值、等于轴值和大于轴值
     *
     * @param arr 待排序数组
     */
    public void quickSortVersion_2(int[] arr) {
        if (arr == null || arr.length == 0) return;
        quickSortV_2(arr, 0, arr.length - 1);
    }

    private void quickSortV_2(int[] arr, int left, int right) {
        if (left < right) {
            int[] partition = partitionV_2(arr, left, right);
            quickSortV_2(arr, left, partition[0] - 1);
            quickSortV_2(arr, partition[1] + 1, right);
        }
    }

    private int[] partitionV_2(int[] arr, int left, int right) {
        int i = left - 1, j = right, k = left, value = arr[left];
        // 假定0-i为小于value，j及其之后为大于value，均为其边界
        while (k <= j) {
            if (arr[k] > value) { // 大于轴值，就放置在右边，并且右边界左移一位
                swap(arr, k, j);
                j--;
            } else if (arr[k] < value) { // 小于轴值，放置在左边，左边界右移一位
                i++;
                swap(arr, k, i);
            } else { // 等于轴值，不移动，即放置在中间，直接后移即可
                k++;
            }
        }
        return new int[]{i + 1, j}; // 返回数组中等于轴值的这些数排序后的端点下标
    }

    /**
     * 快排第三个版本，改动部分为轴值的选择为随机选择
     *
     * @param arr 待排序数组
     */
    public void quickSortVersion_3(int[] arr) {
        if (arr == null || arr.length == 0) return;
        quickSortV_3(arr, 0, arr.length - 1);
    }

    private void quickSortV_3(int[] arr, int left, int right) {
        if (left < right) {
            int[] partition = partitionV_3(arr, left, right);
            quickSortV_2(arr, left, partition[0] - 1);
            quickSortV_2(arr, partition[1] + 1, right);
        }
    }

    private int[] partitionV_3(int[] arr, int left, int right) {
        int i = left - 1, j = right, k = left;
        // 随机选择一个值作为轴值
        int index = left + (int) (Math.random() * (right - left));
        int value = arr[index];
        // 假定0-i为小于value，j及其之后为大于value，均为其边界
        while (k <= j && i < j) {
            if (arr[k] > value) { // 大于轴值，就放置在右边，并且右边界左移一位
                swap(arr, k, j);
                j--;
            } else if (arr[k] < value) { // 小于轴值，放置在左边，左边界右移一位
                i++;
                swap(arr, k, i);
            } else { // 等于轴值，不移动，即放置在中间，直接后移即可
                k++;
            }
        }
        return new int[]{i + 1, j}; // 返回数组中等于轴值的这些数排序后的端点下标
    }

    private void swap(int[] arr, int left, int right) {
        int temp = arr[left] ^ arr[right];
        arr[left] = arr[left] ^ temp;
        arr[right] = arr[left] ^ temp;
    }




}
